1. Field of the Invention
This invention relates generally to set membership proofs in data processing systems whereby a proving mechanism proves to a verifying mechanism that a value secret to the proving mechanism is a member of a public set.
2. Description of the Related Art
Many cryptographic processes performed in data processing systems use a proving mechanism (prover) to prove to a verifying mechanism (verifier) that a secret value of the prover lies in a published set of values. Such set membership proofs are fundamental for building privacy and security into operation of numerous types of data processing systems in their increasing involvement in the tasks of everyday life. An exemplary system might involve a laptop, mobile phone or other data processing device in communication with a remote device, e.g. a server via the Internet, with a view to accessing a restricted service or other resource. Another example might involve some form of smart-card reader reading an inserted card, with communication occurring between the card reader and a processor on the card, or between the reader and a remote verifier mechanism, to verify parameters encoded in the card. The set membership proof itself could form the basis of various tasks implemented by the data processing system, for instance demonstrating possession of a certificate with an attribute in a given set. For example, an id card stating that one lives in a particular town, or that a certificate is still valid, i.e. that the certificate is contained on a list of valid certificates. Numerous other systems and applications involve use of this basic cryptographic process. In general, set membership proofs can be performed for any defined set of values. These may be arbitrary values, or a set of consecutive values. In the latter case, the proof involves proving that a secret value lies in a given interval [A,B] and is often referred to as a range proof.
Like many cryptographic processes, set membership proofs involve the concept of “commitment”. If a prover wants to commit to a secret value σ, the prover can hide the secret into a commitment C and release the commitment to the verifier. For example, a standard method to cryptographically commit to a secret σ is to randomly choose a value rεR[1, p−1] and compute C=gσhr (mod p), where p is a prime number, and g and h are generators of a group G which is the multiplicative group of integers modulo p. The commitment C is perfectly hiding (meaning that it will leak no information about the secret σ) and computationally binding (meaning that bounded computational resources ensure the prover cannot cheat on the value of the secret σ). Along with the commitment, the prover will often also have to provide a “proof of knowledge” to the verifier. The proof of knowledge demonstrates to the verifier the fact to be proved about the secret in question, in this case that the secret value lies in the required set. The proof of knowledge protocol typically involves the sending of a further commitment, followed by steps of challenge and response, whereby the protocol commitment is sent to the verifier, the verifier sends a challenge to the prover, and the prover responds to the verifier enabling the verifier to verify what is to be proved. Ideally, the proof of knowledge will be a “zero-knowledge” proof, meaning that it does not reveal to the verifier anything other than the particular fact(s) to be proved.
Various set membership proofs are known in the art. These prior techniques rely on use of cryptographic algorithms to prove that the secret value has certain properties which are appropriate to the range or other set in question. For instance, it might be demonstrated that a binary representation of the secret value has sufficiently many bits for the required range. As another example, it might be proved that a secret value σ lies in an interval [A,B] by demonstrating that (B−σ) and (σ−A) are both positive. Particular examples of prior techniques are described in the following: Boudot, “Efficient proofs that a committed number lies in an interval”, EUROCRYPT, pp. 431-444, 2000; Lipmaa, “Statistical zero-knowledge proofs from diophantine equations”, Cryptology ePrint archive, Report 2001/086,2001; Lipmaa, “On Diophantine complexity and statistical zero-knowledge arguments”, In Chi-Sung Laih, editor, ASIACRYPT, volume 2894 of Lecture Notes in Computer Science, pp. 398-415, Springer 2003; Schoenmakers, “Some efficient zero knowledge proof techniques”, Monte Verita, March 2001; and Schoenmakers, “Interval proofs revisited”, Milan, Italy, September 2005. However, depending on the size of the set in question, these proofs are not efficient or, in the case of range proofs, are not accurate (i.e. for the proof to work the secret value has to lie in a smaller interval).